题目分析
合法的二叉搜索树,这个题目非常简单,并不是想为难大家,只是希望小伙伴们能够用不同的方法解决此题。
递归
最简单的方法是进行中序遍历,用一个容器接收数据,然后看这个容器中的元素是否满足严格递增的关系。
算法的**时间复杂度为$O(n)$,空间复杂度为$O(n)$**。
1 | #include<iostream> |
优化递归
因为我们每次只要记录前一个数字即可,因此我们设定一个指针pre指向前一个节点。判断一个树是否为搜索树,就是根节点的左子树是搜索树,并且根节点的值大于pre指向的节点的值,再让pre指向根节点,最后判断右子树即可。
算法的**时间复杂度为$O(n)$,空间复杂度为$O(n)$**。
1 | class Solution { |
迭代
中序遍历是可以通过迭代进行的,先访问左子树,在访问左子树之前将根节点加入容器,然后容器的尾部就是最左端的节点,取出该节点,访问其右子树,在访问右子树的过程中也是先访问其左子树。
算法的**时间复杂度为$O(n)$,空间复杂度为$O(n)$**。
1 | #include<iostream> |
刷题总结
在几天前给小伙伴们介绍了二叉搜索树的第k大节点这个题目,和本题非常类似,希望小伙伴们可以学习不同的解法,在面试中也能给自己加分。